package com.AC.ACYuanFuDao;

import org.junit.Test;

import java.util.*;

/**
 * 猿辅导第一题
 */
public class test1 {

    private static class TreeNode{
        int val;

        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i<n; i++){
            nums[i] = sc.nextInt();
        }
        sc.close();
        TreeNode root = buildTree(nums, 0);
        getRoundList(root).forEach(e -> System.out.print(e + " "));
    }

    public static TreeNode buildTree(int[] nums, int index){
        if(index > nums.length - 1) return null;
        TreeNode root = new TreeNode(nums[index]);

        root.left = buildTree(nums, index * 2 + 1);
        root.right = buildTree(nums, index * 2 + 2);

        return root;
    }


    static List<Integer> res = new ArrayList<>();

    static List<List<Integer>> curRes = new ArrayList<>();

    static List<Integer> leafList = new ArrayList<>();

    public static void outTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return;

        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> curList = new ArrayList<>();
            for(int i = 0; i<len; i++){
                TreeNode cur = queue.poll();
                curList.add(cur.val);
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
            }
            System.out.println(curList);
        }

    }

    public static List<Integer> getRoundList(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return res;

        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> curList = new ArrayList<>();
            for(int i = 0; i<len; i++){
                TreeNode cur = queue.poll();
                curList.add(cur.val);
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
            }
            curRes.add(curList);
        }

        for(List<Integer> list : curRes){
            res.add(list.get(0));
        }

        for(int i = 1; i<=curRes.get(curRes.size()-1).size()-1; i++){
            res.add(curRes.get(curRes.size()-1).get(i));
        }

        if(curRes.get(curRes.size()-1).size() < (int) Math.pow(2,curRes.size()-1)){
            int start = (int)Math.sqrt(curRes.get(curRes.size()-1).size()+1);
            while(start < curRes.get(curRes.size()-2).size()){
                res.add(curRes.get(curRes.size()-2).get(start++));
            }
        }



        for(int i = curRes.get(curRes.size()-1).size() < (int) Math.pow(2,curRes.size()-1) ?
                curRes.size()-3 : curRes.size() - 2; i >= 0; i--){
            res.add(curRes.get(i).get(curRes.get(i).size()-1));
        }

        return res;
    }

    @Test
    public void test(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        TreeNode nodeX = buildTree(new int[]{1,2,3,4,5,6,7,8,9}, 0);
        outTree(nodeX);
      getRoundList(nodeX).forEach(System.out::println);
    }

    @Test
    public void test2(){
        System.out.println((int)Math.sqrt(3));
        System.out.println((int)Math.sqrt(4));
        System.out.println((int)Math.sqrt(5));
    }
}
























